#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : ScoreAfterFlippingMatrix.py
# @Time    : 2020/12/7 10:20
# @Description:
from typing import List


class Solution:
    def matrixScore(self, A: List[List[int]]) -> int:
        """
        We have a two dimensional matrix A where each value is 0 or 1.

        A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s
        to 1s, and all 1s to 0s.

        After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of
        the matrix is the sum of these numbers.

        Return the highest possible score.

        Example 1:
            Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
            Output: 39
            Explanation:
                Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
                0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

        Note:
            1. 1 <= A.length <= 20
            2. 1 <= A[0].length <= 20
            3. A[i][j] is 0 or 1.

        :param A:
        :return:
        """
        for i in range(len(A)):
            if A[i][0] == 0:
                A[i] = [1 - tmp for tmp in A[i]]
        for j in range(1, len(A[0])):
            cnt1 = sum(A[i][j] for i in range(len(A)))
            if cnt1 < len(A) / 2:
                for i in range(len(A)):
                    A[i][j] = 0 if A[i][j] else 1
        ans = 0
        for i in range(len(A)):
            t = A[i][::-1]
            item = [val * 2 ** idx for idx, val in zip(range(len(t)), t)]
            ans += sum(item)

        return int(ans)

    def matrixScore2(self, A: List[List[int]]) -> int:
        m, n = len(A), len(A[0])

        ans = m * (1 << (n - 1))

        for j in range(1, n):
            n_ones = 0
            for i in range(m):
                if A[i][0] == 1:
                    n_ones += A[i][j]
                else:
                    n_ones += (1 - A[i][j])
            k = max(n_ones, m - n_ones)
            ans += k * (1 << (n - j - 1))
        return ans


if __name__ == '__main__':
    S = Solution()
    A = [[0, 0, 1, 1], [1, 0, 1, 0], [1, 1, 0, 0]]
    # print(S.matrixScore(A))
    print(S.matrixScore2(A))
    print('done')
